package com.heima.algorithm.recursion_multi;
import java.util.LinkedList;

/**
 * 汉诺塔  T(n) = 2T(n - 1) + c 时间复杂度为O(2^n)
 */
public class HanoiTower {
    static LinkedList<Integer> pillar1 = new LinkedList<>(); // 柱子1
    static LinkedList<Integer> pillar2 = new LinkedList<>(); // 柱子2
    static LinkedList<Integer> pillar3 = new LinkedList<>(); // 柱子3

    /**
     * 对外界提供的move方法
     * @param diskNum 第一根柱子上有多少盘
     */
    public static void move(Integer diskNum) {
        initPillar1(diskNum);
        printPillars();
        move(diskNum, pillar1, pillar2, pillar3);
    }

    /**
     * 移动指定数量的光盘，通过中介柱子把源地的光盘移动到目的地
     * @param diskNum 要移动光盘的数量
     * @param source 源地址
     * @param by 中介
     * @param destination 目的地
     */
    private static void move(Integer diskNum, LinkedList<Integer> source, LinkedList<Integer> by, LinkedList<Integer> destination) {
        if (diskNum == 0) {
            return;
        }
        move(diskNum - 1, source, destination, by);
        destination.addLast(source.removeLast());
        printPillars();
        move(diskNum - 1, by, source, destination);
    }

    /**
     * 打印三根柱子的状态
     */
    private static void printPillars() {
        System.out.println(pillar1);
        System.out.println(pillar2);
        System.out.println(pillar3);
        System.out.println("_________________________");
    }

    /**
     * 初始化柱子1
     *
     * @param diskNum 圆盘个数
     */
    private static void initPillar1(Integer diskNum) {
        if (diskNum == 0) {
            return;
        }
        pillar1.addLast(diskNum);
        initPillar1(diskNum - 1);
    }
}
